package middle;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution_105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        TreeNode root = new TreeNode(preorder[0]), parent = root;
        Stack<TreeNode> stack = new Stack<>();
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = new TreeNode(preorder[i]);
            // 父节点在中序遍历的位置
            Integer parentIndex = map.get(parent.val);
            // 当前节点在中序遍历的位置
            Integer index = map.get(node.val);
            if (index < parentIndex) {
                // 是左孩子
                parent.left = node;
                stack.add(parent);
                parent = node;
            } else {
                // 是右孩子（但是不知道是当前父节点的有孩子，还是祖父节点的右孩子）
                while (!stack.empty() && index >= map.get(stack.peek().val)) {
                    parent = stack.pop();
                }
                parent.right = node;
                parent = node;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution_105 model = new Solution_105();
        TreeNode root = model.buildTree(new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7});
        System.out.println();
    }

    class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
